Search results for "Sweep line algorithm"

showing 2 items of 2 documents

Exact, efficient, and complete arrangement computation for cubic curves

2006

AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in t…

Discrete mathematicsArrangementsControl and OptimizationComputationAlgebraic curvesMathematical analysisBézier curveSweep line algorithmComputer Science ApplicationsModuli of algebraic curvesComputational MathematicsGeometric designComputational Theory and MathematicsFamily of curvesSweep-line algorithmExact geometric computationGeometric primitiveAlgebraic curveGeometry and TopologyRobustnessComputingMethodologies_COMPUTERGRAPHICSMathematicsComputational Geometry
researchProduct

Complete, exact, and efficient computations with cubic curves

2004

The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quart…

Discrete mathematicsModuli of algebraic curvesGeometric designConic sectionComputationFamily of curvesApplied mathematicsGravitational singularityAlgebraic curveSweep line algorithmMathematicsProceedings of the twentieth annual symposium on Computational geometry
researchProduct